"""
难度：中等
如果一个数列 至少有三个元素 ，并且任意两个相邻元素之差相同，则称该数列为等差数列。
例如，[1,3,5,7,9]、[7,7,7,7] 和 [3,-1,-5,-9] 都是等差数列。
给你一个整数数组 nums ，返回数组 nums 中所有为等差数组的 子数组 个数。
子数组 是数组中的一个连续序列。
示例 1：
输入：nums = [1,2,3,4]
输出：3
解释：nums 中有三个子等差数组：[1, 2, 3]、[2, 3, 4] 和 [1,2,3,4] 自身。
示例 2：
输入：nums = [1]
输出：0
提示：
1 <= nums.length <= 5000
-1000 <= nums[i] <= 1000
"""
class Solution:
    # 方法一： 拆分 + 计数
    def numberOfArithmeticSlices(self, nums: List[int]) -> int:
        n = len(nums)
        if n == 1:
             return 0
        d, t = nums[0] - nums[1], 0
        ans = 0
        # 因为等差数列的长度至少为 3，所以可以从i =2 开始枚举
        for i in range(2, n):
            if nums[i-1] - nums[i] == d:
                t += 1
            else:
                d = nums[i-1] - nums[i]
                t = 0
            ans += t
        return ans

    """
    方法二; 动态规划
    定义状态：dp[i]表示从nums[0]到nums[i]且以nums[i]为结尾的等差数列子数组的数量。
    状态转移方程：dp[i] = dp[i-1]+1 if nums[i]-nums[i-1]==nums[i-1]-nums[i-2] else 0
    解释：如果nums[i]能和nums[i-1]nums[i-2]组成等差数列，则以nums[i-1]结尾的等差数列均可以nums[i]结尾，且多了一个新等差数列[nums[i],nums[i-1],nums[i-2]]
    """
    def numberOfArithmeticSlices(self, nums: List[int]) -> int:
        size =  len(nums)
        dp = [0] * size
        for i in range(2, size):
            
            if nums[i] - nums[i-1] == nums[i-1] -nums[i-2]:
                dp[i] = dp[i-1] + 1
            else:
                dp[i] = 0
        return sum(dp)

        